package class05


/*
	给定两个字符串 str1 和 str2, 再给定三个数ic，dc，和rc 分别代表插入，删除和替换一个字符的
	代价，返回将str1编辑成str2的最小代价。
	举例：
		str1="abc",str2="adc",ic=5,dc=3,rc=2从“abc”编辑成“adc”的最小代价是将b替换成d，最小代价是2
	解决：
		分可能性：题目默认拷贝的代价为0
				1. 最后一个字符保留的情况下：
					1.a 最后一个字符相等：
						dp[i][j] = dp[i-1][j-1]
					1.b 最后一个字符不相等：
						dp[i][j] = dp[i-1][j-1] + rc
				2. 最后一个字符不保留的情况下：
					2.a 自身前缀字符串转化为目标串后，将当前字符串删除
						dp[i][j] = dp[i-1][j] + dc
					2.b 自身字符串转化为目标前缀串后，再新增目标串的最后一个字符
						dp[i][j] = dp[i-1][j] + ic

	工作中经常会用到的算法：
		如：搜索：父亲节礼物，自动匹配出：父亲节的礼物

	后续优化：空间优化
*/
func minCost(s1, s2 string, ic, dc, rc int) int {
	dp := make([][]int, len(s1)+1)
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, len(s2)+1)
	}

	for i:=1; i<len(dp[0]); i++ {
		dp[0][i] = i * ic
	}
	for i:=1; i<len(dp); i++ {
		dp[i][0] = i * dc
	}
	for i:=1; i<len(dp); i++ {
		for j:=1; j<len(dp[0]); j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = dp[i-1][j-1] + rc
			}
			dp[i][j] = min(dp[i-1][j] + dc, dp[i][j])
			dp[i][j] = min(dp[i][j-1] + ic, dp[i][j])
		}
	}
	return dp[len(s1)][len(s2)]
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}



















